\section{Análise de código RISCO}

\begin{frame}
\textbf{Análise de código RISCO}
\end{frame}

\begin{frame}
\frametitle{Análise de código RISCO}
\begin{itemize}
  \item Estudo e otimização do código RISCO
  \item Dentro dos objetivos do sistema de compilação (plataforma RISCO-LLVM)
  \item Geração de código: primeiro passo
  \item Duas abordagens:
  \begin{itemize}
    \item Estudo do tamanho do código gerado
    \item Análise estática do grafo de fluxo de controle
  \end{itemize}
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{Densidade do código}
\begin{itemize}
  \item Quantidade de instruções necessárias para a implementação de uma
  determinada funcionalidade (LEFURGY, 1997)
  \item Relevante na área de sistemas embarcados
  \item Metodologia:
  \begin{itemize}
    \item Compara-se o número de instruções emitidas para todos os programas do
    conjunto de testes
    \item 3 arquiteturas: RISCO, MIPS e SparcV8 (só instruções de 4 bytes)
    \item Script em Python calcula o valor a partir do assembly gerado
    \item Testa sob todos os níveis de otimização
  \end{itemize}
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{Densidade do código}
\framesubtitle{Testes}
\scriptsize
\begin{table}[htb]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
\textbf{Arquitetura - Otimização} & \textbf{Mínimo} &
\textbf{Máximo} & \textbf{Média} & \textbf{Desvio padrão} \\ \hline
SPARC - O1 & 40 & 1452 & 558.96 & 340.40 \\ \hline
MIPS - O1 & 52 & 1580 & 561.40 & 341.48 \\ \hline
SPARC - O2 & 40 & 1452 & 566.12 & 342.00 \\ \hline
SPARC - O3 & 40 & 1452 & 566.96 & 342.60 \\ \hline
MIPS - O2 & 52 & 1580 & 569.20 & 344.12 \\ \hline
MIPS - O3 & 52 & 1580 & 569.88 & 344.68 \\ \hline
RISCO - O2 & 52 & 2128 & 735.08 & 452.88 \\ \hline
RISCO - O1 & 52 & 2120 & 748.84 & 467.52 \\ \hline
RISCO - O3 & 52 & 2120 & 766.60 & 474.84 \\ \hline
\end{tabular}
\end{center}
\caption{\footnotesize Resultados da compilação do conjunto de testes para o
         RISCO, MIPS e Sparc, utilizando os 3 níveis de otimização
         (-O1, -O2, -O3): tamanho dos segmentos de instruções dos executáveis,
         em bytes}
\end{table}
\end{frame}


\begin{frame}
\frametitle{Densidade do código}
\framesubtitle{Testes}
\begin{figure}[htb]
  \includegraphics[scale=0.4]{images/grafico-tamanhos}
  \textsf{\caption{\footnotesize
                   Número médio e máximo de instruções emitidas para o conjunto
                   de programas nas 3 arquiteturas.}}
\end{figure}
\end{frame}


\begin{frame}
\frametitle{Densidade do código}
\framesubtitle{Reflexões}
\begin{itemize}
  \item Nenhuma surpresa: os backends MIPS e Sparc são mais maduros
  \item A arquitetura Sparc é similar ao MIPS e RISCO, porém apresenta
  vantagens com relação aos registradores
  \item RISCO: menos padrões de seleção $\rightarrow$ menor espaço de soluções
  na etapa de seleção $\rightarrow$ melhor tempo de compilação
  \item O LLVM não explora totalmente a técnica de atualização do PSW
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{WCET}
\begin{itemize}
  \item Análise da complexidade do código gerado
  \item Tempo de execução no pior caso (\emph{worst case execution time})
  \item Sistemas de tempo real rígido
  \item Problema \alert{indecidível}: redução ao problema da parada
  \item Na prática:
  \begin{itemize}
    \item Aceita uma classe restrita de programas
    \item Determina um \alert{limite superior} para o WCET
    \item Faz diversas suposições sobre a plataforma
  \end{itemize}
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{RISCO-CFG}
\begin{itemize}
  \item Ferramenta para o cálculo do WCET baseado na análise do \emph{grafo de
  controle de fluxo}
  \item Classe restrita de programas
  \item Para cada subrotina, tenta calcular uma fórmula fechada para o seu WCET
  de acordo com os parâmetros da função
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{RISCO-CFG}
\framesubtitle{Grafo de controle de fluxo}
\begin{figure}[htb]
  \includegraphics[scale=0.5]{images/gcf-exemplo}
  \textsf{\caption{Exemplo de grafo de controle de fluxo}}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{RISCO-CFG}
\begin{itemize}
  \item O processo utilizado é o seguinte:
  \begin{enumerate}
    \item Calcula o CFG do código na representação intermediária
    \item Usa componentes de análise e transformação do LLVM para determinar
          os laços naturais e as suas variáveis de indução correspondentes
    \item Usa a variável de indução para determinar o \emph{trip count} de cada
          laço
    \item Calcula o CFG do código na linguagem de montagem
    \item Determina as instruções sintetizadas para cada bloco básico do CFG-IR
    \item Faz uma busca em profundidade no grafo para calcular o WCET
  \end{enumerate}
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{RISCO-CFG}
\framesubtitle{Programa teste}
\scriptsize
\begin{verbatim}
void test_wcet(uint a, uint b, uint c) {
  for (uint i = 5; i < a+10; ++i)
    cout << '*';

  for (uint i = 0; i < b-10; ++i)
    cout << '*';

  for (uint i = c; i < a+b; ++i)
    cout << '*';
}
\end{verbatim}
\end{frame}

\begin{frame}
\frametitle{RISCO-CFG}
\framesubtitle{CFG com informações de laços}
\begin{figure}[htb]
  \includegraphics[scale=0.25]{images/cfg-full}
\end{figure}
\end{frame}


\begin{frame}[fragile]
\frametitle{RISCO-CFG}
\framesubtitle{Algoritmo para cálculo do WCET}
\tiny
\begin{verbatim}
te_memo = { };     // mapeamento nó -> fórmula
te_set = { };      // conjunto das fórmulas já encontradas

função calcula_tecp(node, acumulador_te):
  te_memo[node] = acumulador_te
  acumulador_te += custo(node)
  
  se node contêm a instrução "ret":
    te_set.insert(acumulador_te)
    te_memo.remove(node)
    retorne
  
  se node for o nó final de um laço natural:
    inicio_loop = nó inicial do laço
    custo_interno_loop = acumulador_te - te_memo[inicio_loop]
    custo_loop = custo_interno_loop * #iterações do laço
    
    acumulador_te = te_memo[inicio_loop] + custo_loop
    
    para todo vizinho N de node que não seja inicio_loop:
      calcula_tecp(N, acumulador_te)
  senão:
    para todo vizinho N de node:
      calcula_tecp(N, acumulador_te)

  te_memo.remove(node)
  retorne
\end{verbatim}
\end{frame}


\begin{frame}[fragile]
\frametitle{RISCO-CFG}
\framesubtitle{Resultado}
\begin{columns}[t]
\column{.5\textwidth}
\footnotesize
\begin{itemize}
  \item Subrotina considerada
\end{itemize}
\tiny
\begin{verbatim}
void test_wcet(uint a, uint b, uint c) {
  for (uint i = 5; i < a+10; ++i)
    cout << '*';

  for (uint i = 0; i < b-10; ++i)
    cout << '*';

  for (uint i = c; i < a+b; ++i)
    cout << '*';
}
\end{verbatim}

\column{.5\textwidth}
\footnotesize
\begin{itemize}
  \item WCET calculado
\end{itemize}
\tiny
\begin{verbatim}
4*et_jmp + 10*et_mem + 29*et_arl
+ (5 + a) * (
  et_call + print_char() + 2*et_jmp + 5*et_arl
)
+ (a + b - c) * (
  et_call + et_jmp + print_char() + 4*et_arl
)
- (10 - b) * (
  et_call + print_char() + 2*et_jmp + 5*et_arl
)
\end{verbatim}
\footnotesize
\begin{itemize}
  \item Manipulação simbólica: \emph{SymPy}
\end{itemize}

\end{columns}

\end{frame}